1. Field of the Invention
The present invention relates to an image processing apparatus and an image processing method of performing compression coding on image data.
2. Description of the Related Art
An image forming apparatus such as a printer apparatus temporarily stores image data. In this case, if image data is stored without any change, a high-capacity memory is required, resulting in an increase in cost. In order to solve this problem, image data is compressed and is then stored in a memory.
For example, a print process of the printer apparatus is performed as follows. The printer apparatus receives a page description language (PDL), which is created by, for example, a computer, through a network and analyzes the PDL to generate an intermediate language that can be executed by a rendering unit. The rendering unit analyzes the intermediate language and renders a gradation-processed image to a band memory. The rendered image data is compressed and encoded by a binary image compression coding algorithm, and the generated code data is stored in the memory. Thereafter, during a print operation, the code data is read from the memory in such a way that each of C, M, Y, and K plates is delayed from the preceding thereof, and the read code data is decoded. Then, the decoded data is transmitted to a printer engine corresponding to the data of each of C, M, Y, and K plates and then the printer engine performs printing.
As a technique of effectively compressing data, a technique of performing compression by universal coding has been put into practical use. The universal coding is a lossless data compression scheme and can be applied to various types of data (for example, a character code and an object code) since previous assumption of a statistical nature of an information source is not made when data compression is performed.
A representative universal coding scheme includes Ziv-Lempel coding. For the Ziv-Lempel coding, two algorithms—a universal type and an incremental parsing type—have been suggested. Of these, as a practical scheme using the universal type algorithm, there is Lempel-Ziv-Storer-Syzmanski (LZSS) coding. Meanwhile, as a practical scheme using the incremental parsing type algorithm, there is Lempel-Ziv-Welch coding.
A coding algorithm of LZ77 coding, which is the basis of the LZSS coding, divides coding data into strings of a maximum length each matching a part of a past data string extracted from an arbitrary position thereof and encodes the strings as a duplication of the past data string.
In further detail, it provides a moving window that stores therein already-encoded input data and a look-ahead buffer that stores therein data to be subsequently encoded. All partial strings extracted from a data string in the look-ahead buffer is compared with all partial strings extracted from a data string in the moving window, to obtain a matching partial string with a maximum length between the moving window and the look-ahead buffer. In order to designate the partial string with the maximum length in the moving window, encoding is made with a set of “a start position” and “a matching length” of the partial string with the maximum length and “a next symbol that causes non-matching.”. Next, the encoded data string in the look-ahead buffer is moved to the moving window, and a new data string, length of which corresponds to that of the encoded data string, is input to the look-ahead buffer. Thereafter, the same processing is repeated, so that data is decomposed into partial data strings to be encoded.
Generally, the LZSS coding requires detection to be repeated by a number of times depending on a length of the already-encoded input data in the moving window to obtain longest matching data string between an input data string and the already-encoded input data. Accordingly, the LZSS coding is considered to incur high computational cost but to exhibit high compression rate.
Meanwhile, a coding algorithm of the LZW coding builds a rewritable dictionary. An input character string is parsed into different character strings. The parsed character strings are, in order of arrival, assigned with a number and registered to the dictionary. Then, a currently input character string is represented only by the number assigned to a longest matching character string registered in the dictionary. As compared with the LZSS coding, the LZW coding is lower in compression rate, but is simpler, easier in computation, and can be processed at high speed. For this reason, the LZW coding is widely used for file compression in a storage apparatus, data transmission, etc.
Japanese Patent No. 3240495 discloses a coding technique of judging whether or not multi-byte data can be compression-encoded by the LZ scheme, performing compression encoding on the multi-byte data by LZ scheme when possible, and adding a small-size header to the multi-byte data when compression coding by the LZ scheme is impossible.
In the printer apparatus, in the printing, image data stored in the memory after having been subjected to compression encoding is read from the memory, and is then decoded before it is transmitted to the printer engine. For this reason, a decoding process of the compression-encoded image data needs to keep pace with the printing speed of the printer engine. Thus, for a compression coding scheme applied to the printer apparatus, it is required that a worst compression rate can be explicitly obtained and the amount of codes generated when image data is compressed and encoded at a worst compression rate needs be as small as possible.
Here, there may be a case in which the amount of codes generated at the worst compression rate is much larger than the amount of data of original image data. In this case, it is necessary to check for whether or not a memory access time during decoding an amount of codes obtained through encoding at the worst compression rate is sufficient with respect to the speed of transmitting the decoded image data to the printer engine and whether or not the capacity of the memory is sufficient to store data of an amount of codes obtained through encoding at the worst compression rate. For example, in a complicated compression coding scheme using a discrete cosine transform (DCT) such as Joint Photographic Experts group (JPEG), there is a problem in that it is difficult to obtain the worst compression rate and so it is not easy to design a system.
Meanwhile, it has been known that the LZ77 coding can be applied to photographic image data having a high resolution or photographic image data interpolated by, for example, a bilinear technique. Further, in the LZ77 coding, when encoding cannot be performed in units of one byte, since encoding is performed by adding a header to raw data of one byte, it is possible to easily obtain the worst compression rate for the case in which encoding in units of one bye is not performed at all. However, in this case, since the header is added to every unit of raw data that cannot be encoded in units of one byte, there is a problem in that the encoded data size becomes larger than the data size of original raw data.
According to the technique disclosed in Japanese Patent No. 3240495, when the compression coding cannot be performed by the LZ coding, encoding is performed by adding a header at a head of multi-byte data. Accordingly, it is advantageous, in improving the compression rate, over the case in which the header is added to each unit of raw data (one byte). However, the technique is also problematic in that the maximum matching length in the compression decoding is limited to that of initially judged multi-byte data or below, which leads to deterioration of the compression rate.
Further, in the technique of Japanese Patent No. 3240495, it may be considered to further increase the maximum matching length in order to improve the compression rate. Such a case is problematic in that it is necessary to increase the size of a buffer that temporarily stores data to be encoded, and thus the memory capacity increases.
For example, in an LHZ scheme that is also one scheme included in the LZ scheme, the maximum matching length is 8 kilo bytes, and in a ZIP scheme, the maximum matching length is 32 kilo bytes. Thus, in order to improve the compression rate, it is necessary to use a buffer of 8 kilo bytes and a buffer of 32 kilo bytes in the LHZ scheme and the ZIP scheme, respectively.
Further, in Japanese Patent No. 3240495, when compression coding is performed by a two-path method including: a judgment process on whether or not encoding per one byte unit can be performed; and an encoding process based on the LZ scheme, in order to increase the process speed, it is necessary to use the buffer of 8 kilo bytes or 32 kilo bytes for each of the judgment process and the encoding process, and thus the memory capacity further increases. Further, in the case of performing a pipeline process, it is necessary to additionally use a toggle buffer and further increase the memory capacity.